home *** CD-ROM | disk | FTP | other *** search
/ AI Game Programming Wisdom / AIGameProgrammingWisdom.iso / SourceCode / 04 Pathfinding and Movement / 05 Hancock / ExtractRegions.cpp next >
Encoding:
C/C++ Source or Header  |  2001-08-19  |  5.2 KB  |  144 lines
  1.  
  2.  
  3. LArray2D<bool> NodeMap::RegionConnection; //region connections for all traversable links
  4. LArray2D<bool> NodeMap::DoorRegionConnection; //region connections using non-door links
  5. LArray2D<bool> NodeMap::JumpRegionConnection; //region connections using non-jump links
  6. LArray2D<bool> NodeMap::ElevatorRegionConnection; //region connections using non-elevator links
  7.  
  8.  
  9.  
  10. void NodeMap::GenerateRegionConnectivity(const std::vector<const PathLink *> &oneWayLinks,
  11.                                         LArray2D<bool>& RCMatrix, PathNode::RegionType rtype){
  12.     RCMatrix.Fill(false);
  13.     for (int i=0; i < RCMatrix.rows(); i++)
  14.         RCMatrix(i, i) = true;
  15.  
  16.     for (int j =0; j < (int)oneWayLinks.size(); j++){ //for all one way links
  17.         LList<int> regions;
  18.         const PathLink *link = oneWayLinks[j];
  19.         int start = link->Start()->GetRegion(rtype); //take the start region of the connected link
  20.         int end = link->End()->GetRegion(rtype); //given a link that goes from start to end
  21.         for (int k=0; k < RCMatrix.rows(); k++){ //for every region k
  22.             if (RCMatrix(k, start))  //if k can reach start
  23.                 RCMatrix(k, end) = true; //then k can reach end
  24.         }
  25.     }
  26. }
  27.  
  28. template <class OneWayPred, class ConnectedPred>
  29. int GenerateRegions(std::vector<PathNode *>& nodeList, LVector<const PathLink *> &oneWayLinks,
  30.                           OneWayPred& oneway, ConnectedPred& cpred, PathNode::RegionType rtype)
  31. {
  32.  
  33.     std::vector<PathNode *>::iterator i;
  34.     int connectedRegionCount = 0;
  35.     
  36.     for (i = nodeList.begin(); i != nodeList.end(); i++){
  37.         PathNode *node = (*i);
  38.         if (node->GetRegion(rtype) == 0){ //if we haven't given the node a region yet, put it on the list
  39.             LList<PathNode *> connected;
  40.             connected.push_back(node);
  41.             int currentRegion = ++connectedRegionCount;
  42.             node->SetRegion(rtype, currentRegion);
  43.             while (!connected.empty()){
  44.                 PathNode *n = connected.front();
  45.                 LAssert(n->GetRegion(rtype) == currentRegion);
  46.                 connected.pop_front();
  47.                 for (int j = 0; j < (int)n->links.size(); j++){
  48.                     const PathLink &link = n->links[j];
  49.                     if (cpred(link)){ //if this link is a legal connection
  50.                         if (oneway(link)) //if it is a 1-way link 
  51.                             oneWayLinks.push_back(&link); //put it on the 1-way list
  52.                         else if(link.End()->GetRegion(rtype) == 0) { //else if this link end node hasn't been labelled
  53.                             link.EndNonConst()->SetRegion(rtype, currentRegion); //set the region of the link end node
  54.                             connected.push_back(link.EndNonConst()); //and add it to the connected list
  55.                         }
  56.                     }
  57.                 }
  58.             }
  59.         }
  60.     }
  61.     return connectedRegionCount;
  62. }
  63.  
  64. struct AlwaysTrue{
  65.     bool operator()(const PathLink&){return true;}
  66. };
  67.  
  68. struct NoJump{
  69.     bool operator()(const PathLink& link){ return !(link.flags & PathLink::flagLinkJump);}
  70. };
  71.  
  72. struct NoDoor{
  73.     bool operator()(const PathLink& link){return !(link.flags & PathLink::flagLinkDoor);}
  74. };
  75.  
  76. struct NoElevator{
  77.     bool operator()(const PathLink& link){return !(link.flags & PathLink::flagLinkElevator);}
  78. };
  79.  
  80. struct NormalOneWay{
  81.     bool operator()(const PathLink& link){return !link.GetReturnLink();}
  82. };
  83.  
  84. struct JumpOneWay{
  85.     bool operator()(const PathLink& link){
  86.         const PathLink *retlink = link.GetReturnLink();
  87.         return (!retlink || (retlink->flags & PathLink::flagLinkJump));
  88.     }
  89. };
  90.  
  91. struct DoorOneWay{
  92.     bool operator()(const PathLink& link){
  93.         const PathLink *retlink = link.GetReturnLink();
  94.         return (!retlink || (retlink->flags & PathLink::flagLinkDoor));
  95.     }
  96. };
  97.  
  98. struct ElevatorOneWay{
  99.     bool operator()(const PathLink& link){
  100.         const PathLink *retlink = link.GetReturnLink();
  101.         return (!retlink || (retlink->flags & PathLink::flagLinkElevator));
  102.     }
  103. };
  104.  
  105. void NodeMap::ExtractRegions(){
  106.  
  107.     std::vector<const PathLink *> oneWayLinks;
  108.  
  109.     //compute connected regions and connectivity matrix
  110.     AlwaysTrue truefunc;
  111.     NormalOneWay normal1way;
  112.     int regions = GenerateRegions(nodeList, oneWayLinks, normal1way, truefunc, PathNode::Connected);
  113.     RegionConnection = LArray2D<bool>(regions + 1, regions + 1);
  114.     GenerateRegionConnectivity(oneWayLinks, RegionConnection, PathNode::Connected);
  115.  
  116.  
  117.     //compute no-door regions and connectivity matrix
  118.     oneWayLinks.clear();
  119.     NoDoor nodoor;
  120.     DoorOneWay door1way;
  121.     int noDoorRegions = GenerateRegions(nodeList, oneWayLinks, door1way, nodoor, PathNode::NoDoor);
  122.     DoorRegionConnection = LArray2D<bool>(noDoorRegions + 1, noDoorRegions + 1);
  123.     GenerateRegionConnectivity(oneWayLinks, DoorRegionConnection, PathNode::NoDoor);
  124.     
  125.  
  126.     //compute no-force-jump regions and connectivity matrix
  127.     oneWayLinks.clear();
  128.     NoJump nojump;
  129.     JumpOneWay jump1way;
  130.     int noJumpRegions = GenerateRegions(nodeList, oneWayLinks, jump1way, nojump,
  131.         PathNode::NoJump);
  132.     JumpRegionConnection = LArray2D<bool>(noJumpRegions + 1, noJumpRegions + 1);
  133.     GenerateRegionConnectivity(oneWayLinks, JumpRegionConnection, PathNode::NoJump);
  134.  
  135.     //compute no-elevator regions and connectivity matrix
  136.     oneWayLinks.clear();
  137.     NoElevator noelevator;
  138.     ElevatorOneWay elevator1way;
  139.     int noElevatorRegions = GenerateRegions(nodeList, oneWayLinks, elevator1way, noelevator,
  140.         PathNode::NoElevator);
  141.     ElevatorRegionConnection = LArray2D<bool>(noElevatorRegions + 1, noElevatorRegions + 1);
  142.     GenerateRegionConnectivity(oneWayLinks, ElevatorRegionConnection, PathNode::NoElevator);
  143. }
  144.